Computer science

Write a Python program to solve the popular "Hashiwokakero" or "Bridges" puzzle. The input to your program will be a rectangular array of numbers and dots, for example:

. 1 . . . 6 . . . 7 . . . . 4.4.2 .

. . 4.2 . . 2 . . . 3.8 . . . 6.2

. . . . . 2 . . . . . . . . . . . . . .

5 .

. 7 . .

.

. . 5.6 . . 8.5

. . . . . . . . . . . . . 2 . . . . . .

. . . 5 . . . 9 .

. . 8 .

. 8.4 .

4.5 . . . . . . . . . . . . . . . . 3

. . . . 2 . . 4 . . 1.5 . . . 2 . . .

. 2.7.4 . . . 7.2 . . 5 . . . 3 .

. . . . . . . . . . . . 4 . . 3.1.2

Each number represents an "island", while the dots represent the empty space

(

water

)

\ufeffbetween the islands. Numbers larger than

9

\ufeffare indicated by

\'

\' (10), \'

\' (11)

\ufeffor

\'

\' (12) .

\ufeffThe aim is to connect all the islands with a network of bridges, satisfying these rules:

-

all bridges must run horizontally or vertically

-

bridges are not allowed to cross each other, or other islands

-

there can be no more than three bridges connecting any pair of islands

-

the total number of bridges connected to each island must be equal to the number on the island

For example, after reading the

10 -

line input above, your program might produce the attached out

(

see image below

) .

Note that single bridges are indicated by the characters

\' - \'

\ufeffor

\' | \',

\ufeffpairs of bridges by

\' = \'

\ufeffor

\' " \'

\ufeffand triples by

\'

\'

\ufeffor

\'

\',

\ufeffdepending on whether they run horizontally or vertically. Water between bridges and islands is indicated by space characters

\' \' .

In some cases, there may be many solutions, in which case your program should only print one solution.

Computer science

Answer